﻿#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* PreorderCreate(int* a, int* i)
{
    if (a[*i] == 0)
    {
        (*i)++;
        return NULL;
    }

    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = a[*i];
    (*i)++;
    root->left = PreorderCreate(a, i);
    root->right = PreorderCreate(a, i);
    return root;
}

bool isSameTree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (!root && !subRoot)
        return true;
    if (!root || !subRoot)
        return false;
    if (root->val != subRoot->val)
        return false;
    return isSameTree(root->left, subRoot->left) && isSameTree(root->right, subRoot->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL)
        return false;
    if (root->val == subRoot->val)
    {
        if (isSameTree(root, subRoot))
        {
            return true;
        }
    }
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

int main()
{
    int arr[] = { 1,2,3,4,0,0,4,0,0,3,0,0,2,0,0 };
    int n = 0;
    struct TreeNode* root = PreorderCreate(arr, &n);
    int arr1[] = { 3,4,0,0,4,0,0 };
    int t = 0;
    struct TreeNode* subroot = PreorderCreate(arr1, &t);
    bool flag = isSubtree(root,subroot);
    if (flag)
        printf("subroot是root的子树\n");
    else
        printf("subroot不是root的子树\n");
    return 0;

}